<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>
<body>

  <script>
    /*
      计数排序: 数组排序算法的一种

      逻辑:
        1. 准备一个新的数组
          => 遍历原始数组, 把原始数字当做新数组的索引向新数组内填充数据
          => 新数组的数据按照计数排列
        2. 遍历新数组
          => 把索引在当做数据放进原始数组内
          => 前提: 把原始数组清空
    */

    // 实现
    // 准备一个原始数组
    // var origin = [ 9, 3, 100, 6, 4, 100, 1, 9, 8, 7, 2, 2, 5, 100, 3, 32, 55 ]
    // console.log('原始数组 : ', origin)
    // // 准备一个新数组
    // var newarr = []

    // // 1. 步骤一: 遍历原始数组, 把每一个数据当做新数组的索引去添加到新数组内
    // for (var i = 0; i < origin.length; i++) {
    //   // origin[i] 表示的是原始数组内的真实数据
    //   // 目的: 把原始的真实数据当做索引使用
    //   // 我们要把值的位置当做计数器使用
    //   //
    //   !newarr[ origin[i] ] ? newarr[ origin[i] ] = 1 : newarr[ origin[i] ]++
    // }

    // console.log('新数组 : ', newarr)

    // // 2. 步骤2: 把新数组内的索引, 当做数据还原到 origin 内, 把新数组内的值, 当做个数插入
    // // 归零 origin
    // origin.length = 0
    // console.log('origin 归零 : ', origin)

    // 遍历新数组
    // for (var i = 0; i < newarr.length; i++) {
    //   // 2-1. 如果当前 [i] 位置没有数据, 那么循环的本次不需要了
    //   if (!newarr[i]) continue

    //   // 2-2. 把有数据位置的索引 i 当做真实数据, 追加到 origin 内
    //   // 问题: 所有的都直接追加吗 ?
    //   //   值为 1 的, 直接追加, 否则的话, 值是多少, 追加多少个
    //   if (newarr[i] === 1) {
    //     origin[origin.length] = i
    //   } else {
    //     // 值是多少, 追加多少个, 循环来追加
    //     // 问题: 循环多少次, 值是多少, 循环多少次
    //     for (var k = 0; k < newarr[i]; k++) {
    //       origin[origin.length] = i
    //     }
    //   }

    //   console.log(i)
    // }

    // for (var i = 0; i < newarr.length; i++) {
    //   // 2-1. 如果当前 [i] 位置没有数据, 那么循环的本次不需要了
    //   if (!newarr[i]) continue

    //   // 2-2. 把有数据位置的索引 i 当做真实数据, 追加到 origin 内
    //   // 当前这个索引位置上的值是多少, 就向 origin 内追加多少个当前索引数字
    //   for (var k = 0; k < newarr[i]; k++) origin[origin.length] = i
    // }


    // console.log('排序之后 : ', origin)


    // 计数排序
    var origin = [ 9, 3, 100, 6, 4, 100, 1, 9, 8, 7, 2, 2, 5, 100, 3, 32, 55 ]
    var newarr = []

    // 1. 把数据当索引
    for (var i = 0; i < origin.length; i++) {
      // origin[i] 就是数据
      newarr[ origin[i] ] ? newarr[ origin[i] ]++ : newarr[ origin[i] ] = 1
    }

    // 2. newarr 中的索引当数据
    //    newarr 中的值当多少个
    // 2-1. 清空 origin
    origin.length = 0
    // 2-2. 填充回去
    for (var i = 0; i < newarr.length; i++) {
      // i 表示真实数据
      // newarr[i] 表示有多少个
      if (!newarr[i]) continue

      // 填充回去
      // 填充 newarr[i] 个 i
      for (var k = 0; k < newarr[i]; k++) origin[origin.length] = i
    }

    console.log('排序之后 : ', origin)
















    // 问题: 如何判断一个数组内有没有某一个索引位置的数据 ?
    // 索引可以访问数组内的数据
    //   如果有该索引位置, 那么就是该索引位置的数据
    //   如果没有该索引位置, 那么就是 undefined
    // 根据我的设置
    //   原先有就是 ++, 原先没有就是 = 1
    // 如果我拿到数组内某一个索引位置是 undefined, 说明之前没有过
    //   只要之前有过, 那么一定是一个正整数
    // console.log(newarr[1])
    // if (newarr[1] === undefined) newarr[1] = 1
    // else newarr[1]++
    // console.log(newarr)


    // 某一个索引位置的数据只有两种情况
    //   1. undefined      false
    //   2. 正整数          true
    // if (!newarr[1]) newarr[1] = 1
    // else newarr[1]++
    // console.log(newarr)

    // 标准的 if else 语句, 转换成 三元表达式
    // !newarr[1] ? newarr[1] = 1 : newarr[1]++
    // console.log(newarr)



















    // 逻辑
    // var origin = [ 2, 3, 2, 6, 5]
    // console.log(origin)

    // var newarr = []
    // newarr[2] = 1
    // newarr[3] = 1
    // newarr[2]++
    // newarr[6] = 1
    // newarr[5] = 1

    // console.log(newarr)

    // origin = []

    // console.log(origin)

    // origin[origin.length] = 2
    // origin[origin.length] = 2
    // origin[origin.length] = 3
    // origin[origin.length] = 5
    // origin[origin.length] = 6

    // console.log(origin)

  </script>
</body>
</html>
